1. Field of the Invention
Certain embodiments of the present invention are related to methods for distributing datagrams across a network to a number of different destinations. Certain other embodiments of the present invention are related to systems that can provide for implementation of the above-discussed methods.
2. Description of the Related Art
Datagrams such as, but not limited to, packets, cells, and bit strings, are often replicated and distributed across a communications network in a broadcast or multicast format, thereby reaching a plurality of destinations in the network. In a representative broadcast or multicast, multiple network nodes, virtual local access networks (VLANs), etc., may receive replications of the datagram. One related-art system for distributing a datagram to a plurality of VLANs is illustrated in FIG. 1.
According to the related-art system illustrated in FIG. 1, a datagram 100 that is to be broadcast or multicast enters a first router 105 through a first ingress 110. Once in the first router 105, the datagram 100 illustrated in FIG. 1 is replicated and forwarded to the first egress 115 and second egress 120 of the first router 105. The replicated datagram 100 that is forwarded to the second egress 120 is then transmitted to the third router 125 via the third ingress 130. However, because, in FIG. 1, the third router 125 is not operably connected to any destinations to which the datagram 100 is to be transmitted, the datagram 100 that reaches the third router 125 does not exit through any egress of the third router 125.
The datagram 100 that is transmitted through the first egress 115 of the first router 105 enters the second router 135 through the second ingress 140 thereof. The second router 135 illustrated has four egress ports 145, 150, 155, 160, and each of these egress ports is operably connected to one or more VLANs (VLAN #1, VLAN #2, VLAN #3). The datagram 100 may be forwarded to any and/or all of these VLANS via, for example, a multicast or broadcast.
As illustrated in FIG. 1, the second router 135 includes a first egress port 145, a second egress port 150, and a third egress port 155 that are each operably connected to VLAN #1. The third egress port 155 and fourth egress port 160 illustrated in FIG. 1 are each operably connected to VLAN #2, and the second egress port 150 and third egress port 155 are each operably connected to VLAN #3.
In some situations, it may be desirable for the datagram 100 to be forwarded exclusively to those egress ports of the second router 135 that are operably connected to VLAN #1. If the second router 135 finds itself in such a situation, the second router 135 may behave as illustrated in FIG. 2A, wherein the datagram 100, after being replicated three times, egresses from the second router 135 through the first port 145, second port 150, and third port 155, that are each operably connected to VLAN #1.
FIG. 2B illustrates a situation wherein the second router 135 replicates and transmits the datagram 100 through the third port 155 and fourth port 160 in order to allow the datagram 100 to be forwarded to VLAN #2. In FIG. 2B, the datagram 100 is only replicated twice and is sent through the third egress port 155 and fourth egress port 160.
FIG. 2C illustrates a situation wherein the second router 135 replicates and transmits a datagram 100 to each of the ports that are operably connected to VLAN #1 and VLAN #2. As shown in FIG. 2C, in order to perform this task, the datagram 100 is replicated five times by the second router 135. Then, one replicated datagram is forwarded to each of the first, second, and third ports, 145, 150, 160, respectively. However, because the third port 155 is operably connected to both VLAN #1 and VLAN #2, two replicated datagrams 100 are forwarded to the third port 155 and transmitted therefrom.
It should be noted that the replicated and forwarded datagrams 100 discussed throughout this document may be either routed or bridged. An example of the related-art mechanics involved with replicating and forwarding a routed or bridged datagram 100 to the various egresses discussed above is explained in more detail with reference to FIG. 3.
FIG. 3 illustrates yet another embodiment of a datagram 100 that enters the second router 135 illustrated in FIG. 1 through the second ingress port 140. As illustrated in FIG. 3, once the datagram 100 has entered the second router 135, it proceeds into the Address Resolution Logic ARL) 300 of the router 135. The ARL 300 shown includes an Internet Protocol Multicast (IPMC) controller 305 through which the datagram 100 also proceeds. According to the related art, the IPMC controller 305 replicates the datagram 100 and forwards the replicated datagram 100 to memory units 310, 315, 320, 325 that are each associated with and operably connected to one of the ports/egresses 145, 150, 155, 160, respectively.
According to the related art router 135, each of the memory units 310, 315, 320, 325 include an IPMC table 330 that is referenced by the IPMC controller 305. The IPMC table 330 in a particular memory unit, in turn, references a Most Significant Bit (MSB) table 335 and a Least Significant Bitmap (LSB) table 340 that are each also included in that particular memory unit.
The MSB table 335 and LSB table 340 in each related-art memory unit shown in FIG. 3 are used to determine whether the datagram 100 is to be forwarded through the port or egress to which the memory unit in question is associated with. The related-art MSB table 335 and LSB table 340 discussed above are also used and to determine whether multiple replications of the datagram 100 are to be transmitted via the egress associated with the memory unit in question.
The related art router 135 illustrated in FIG. 3 suffers from several shortcomings. For example, because separate memory units 310, 315, 320, 325 are associated with each of the router's egress ports, and because each of these memory units separately determines both whether the particular egress that it is operably connected to is to transmit a replicated copy of the datagram 100 and how may replications are to be transmitted from that particular egress, a large amount of memory is typically required in the related-art router 135.
Another shortcoming of the related-art router 135 have to do with the fact that, when a set of datagrams enters the router 135 in succession through the ingress port 140, the IPMC controller 305 queues up incoming datagrams and, when appropriate, each datagram is transmitted by the router 135 according to the sequence in which the datagram arrived. Such a procedure becomes particularly undesirable when some of the queued up datagrams 100 are particularly large and therefore require a substantial amount of processing by the router 135, at least relative to smaller datagrams 100. In such situations, the amount of time that has to be devoted to processing the larger datagrams 100 may slow down the overall operation of the router 135 and/or may lead to loss/dumping of certain datagrams 100 if they cannot be stored in or processed quickly enough through the router 135.
Another disadvantage of the router 135 according to the related art has to do with the fact that the router 135 cannot prioritize datagrams. For example, if a datagram 100 from a high-priority class of service (COS) reaches an ingress 140 of the related-art router 135 illustrated in FIG. 1, this “high-priority” datagram may be forced to wait in a queue until lower-priority datagrams from other COSs, which were received first, are processed. In others words, one shortcoming of data distribution devices according to the related art is that all datagrams that these datagrams receive have to wait their turn, regardless of their level of priority.
In addition to the above, the fact that the related art router 135 illustrated in FIG. 3 includes separate tables or sets of instructions at every egress to determine whether a datagram is to be replicated and/or transmitted across a port that is operably connected to that egress is inefficient. It would be preferable to have fewer tables to reference and store in memory.
At least in view of the above, it is an object of certain embodiments of the present invention to provide methods and systems that allow for fewer tables or sets of instructions to be used in order to multicast or broadcast a datagram across a set of ports or egresses. It is also an object of certain embodiments of the present invention to provide methods and systems that reduce the amount of total memory that is used when multicasting or broadcasting a datagram. Even further, it is an object of certain embodiments of the present invention to provide methods and systems that allow for prioritizing of the replication and/or transmission of datagrams entering a data distribution device through an ingress.